1. Field
The present invention relates generally to parallel computing, and more specifically, to methods and systems for conditioning an algorithm for parallel execution.
2. Background
Genetic algorithms in programming have existed for quite a long time. Attempts have been made to try to solve real world problems, such as non-linear optimization, with pure genetic algorithms. Pure genetic algorithms include algorithms that create mappings between real world problems to totally stochastic and evolutionary notions. Hybrid algorithms that couple a genetic framework with technical algorithms have also been tried in the past. However, in all cases, the focus of parallel fast execution has been limited to the obvious parallel run of generations. Moreover, it appears that no systematic approach exists in defining the optimal conditions for hybrid collaboration techniques.
Non-linear optimization problems occur in many real-world problems. The mathematical algorithms for solving those problems are typically large and sequential in nature. That means the algorithms start with a first initial estimate vector and provide a mechanism for producing a next vector. Each new vector improves an objective function. In many important real world cases, generating the sequence of vectors or numbers that converge to a solution is a long running process. Such algorithms are usually impossible to parallelize and, consequently, serial computations are the only way to reach a solution. In many cases, large computers may spend days performing computations in order to solve a given problem.
Using genetic algorithms or evolutionary strategies in programming is not a new practice. A genetic algorithm is comprised of a component that produces an initial population of possible solutions, a best fit component that emulates the natural selection process, and a component that emulates the mutation and genetic crossover. The creation of new off-springs and best fit selection continue until the solution cannot be improved any more or the number of generations exceeds some predetermined upper boundary. Historically, such pure genetic algorithms do not yield good solutions and seem to produce results in an aimless manner for a long number of generations.
Hybrid genetic algorithms adapt a pure numerical algorithm to a genetic algorithmic framework. In a way, the pure numerical algorithm defines a target and bounds the scope of the genetic experiment in converging to a solution. Hybrid genetic algorithms may be executed serially but are well suited for parallel computing. Serial hybrid genetic algorithms do not provide any real tangible benefit and are done as academic exercises. On the other hand, executing hybrid genetic algorithms in parallel can provide improvement over other algorithms for many specialized business problems.
Existing hybrid genetic algorithms do not provide a systematic way of defining the genetic parameters that can condition a numerical algorithm to perform optimal in a parallel computational context. Choices, such as number of parallel generations, number of mutations within a generation, and the genetic crossover, have remained experimental and non-deterministic. Seemingly, published crossover techniques all utilize a “wait-to-complete” approach which defeats the optimization effect. This is because, at each genetic stage, a controller needs to wait for all the generations to complete mutations before it can initiate best fit and crossover computations. Existing techniques do not provide guidelines for selecting the optimal number of parallel independent families. It has been observed in most cases that going beyond the optimal number deteriorates performance.
Hence, it would be desirable to provide methods and systems that are capable of conditioning the way numerical algorithms will be executed in a parallel configuration to ensure optimum elapsed time using a genetic framework in an efficient manner.